package datastructure
{
	import Util.DrawTree;
	
	import data.AppConfig;
	
	import flash.display.MovieClip;
	import flash.display.Sprite;

	/**
	 * 红黑树的性质：
	 * 1)每一个节点或者着红色,或者着成黑色. 
	 * 2)根是黑色的 
	 * 3)如果一个节点是红色的,那么它的子节点必须是黑色的. 
	 * 4)从一个节点到一个NULL指针的每一条路径必须包含相同数目的黑色节点. 
	 * @author Administrator
	 * 
	 */	
	public class RBTree
	{
		private var _size:int;
		
		private var NIL:RBTreeNode = new RBTreeNode(-1);
		private var _root:RBTreeNode = NIL;
		//private var position:RBTreeNode;
		
		public function RBTree()
		{
			
		}
		
		public function get root():RBTreeNode
		{
			return this._root;
		}
		
		public function get size():int
		{
			return this._size;
		}
		
		/**
		 * 构建红黑树 
		 * @param nodes
		 * 
		 */		
		public function buildRBTree(nodes:Array):void
		{
			for(var i:int = 0; i < nodes.length; i++)
			{
				insert(nodes[i]);
			}
			setAllNodesDistance(this._root);
		}
		
		/**
		 * 左旋 
		 * @param root 红黑树
		 * @param pos 发生左旋的节点
		 * 
		 */		
		private function leftRotate(root:RBTreeNode,pos:RBTreeNode):void
		{
			//trace("左旋：" + pos.key + ";" + pos.right.key);
			var rcNode:RBTreeNode = pos.right;
			pos.right = rcNode.left;
			if(rcNode.left != NIL)
			{
				rcNode.left.parent = pos;
			}
			rcNode.parent = pos.parent;
			if(pos.parent == NIL)
			{
				this._root = rcNode;
			}
			else if(pos == pos.parent.left)
			{
				pos.parent.left = rcNode;
			}
			else
			{
				pos.parent.right = rcNode;
			}
			rcNode.left = pos;
			pos.parent = rcNode;
			
		}
		
		/**
		 * 右旋 
		 * @param root 红黑树
		 * @param pos 发生右旋的节点
		 * 
		 */		
		private function rightRotate(root:RBTreeNode,pos:RBTreeNode):void
		{
			//trace("右旋：" + pos.key);
			var lcNode:RBTreeNode = pos.left;
			pos.left = lcNode.right;
			if(lcNode.right !=NIL)
			{
				lcNode.right.parent = pos;
			}
			lcNode.parent = pos.parent;
			if(pos.parent == NIL)
			{
				this._root = lcNode;
			}
			else if(pos == pos.parent.left)
			{
				pos.parent.left = lcNode;
			}
			else
			{
				pos.parent.right = lcNode;
			}
			lcNode.right = pos;
			pos.parent = lcNode;
		}
		
		
		/**
		 * 插入新节点 
		 * @param node
		 * @return 
		 * 
		 */		
		public function insert(k:RBTreeNode):void
		{
			var y:RBTreeNode = NIL;
			var x:RBTreeNode = this._root;
			//var z:RBTreeNode = new RBTreeNode(k);
			var z:RBTreeNode = k;
			z.parent = z.left = z.right = NIL;	//初始化
			
			while(x != NIL)	//找到要插入的位置
			{
				y = x;
				if(z.key < x.key)
				{
					x = x.left;
				}
				else
				{
					x = x.right;
				}
			}
			//和周边店增加关系
			z.parent = y;
			if(y == NIL)
			{
				this._root = z;
			}
			else
			{
				if(z.key < y.key)
				{
					y.left = z;
				}
				else
				{
					y.right = z;
				}
			}
			//trace("插入节点:" + z.key);
			
			z.left = z.right = NIL;
			z.color = AppConfig.RED;
			RBTreeInsertFixUp(z);
		}
		
		/**
		 * 新节点插入修正程序
		 * case 1:z的叔叔y是红色的
		 * case 2:z的叔叔y是黑色的，而且z是右孩子
		 * case 3:z的叔叔y是黑色的，而且z是左孩子
		 * @param root 红黑树
		 * @param z 需要修正的节点
		 * 
		 */		
		private function RBTreeInsertFixUp(z:RBTreeNode):void
		{
			//trace("fixup:" + z.key);
			while(z.parent.color == AppConfig.RED)
			{
				if(z.parent == z.parent.parent.left)	//y在右边
				{
					
					var y:RBTreeNode = z.parent.parent.right;
					if(y.color == AppConfig.RED)	//case 1
					{
						z.parent.color = AppConfig.BLACK;
						y.color = AppConfig.BLACK;
						z.parent.parent.color = AppConfig.RED;
						z = z.parent.parent;
					}
					else
					{
						if(z == z.parent.right)	//case 2
						{
							z = z.parent;
							leftRotate(this._root,z);//case 2转化为case 3
							//trace("左旋结束："  + z.key + " " + z.parent.key+ " " + z.parent.parent.key);
						}
						z.parent.color = AppConfig.BLACK;
						z.parent.parent.color = AppConfig.RED;
						rightRotate(this._root,z.parent.parent);
					}
				}
				else	//y在左边
				{
					var y1:RBTreeNode = z.parent.parent.left;
					if(y1.color == AppConfig.RED)
					{
						z.parent.color = AppConfig.BLACK;
						y1.color = AppConfig.BLACK;
						z.parent.parent.color = AppConfig.RED;
						z = z.parent.parent;
					}
					else
					{
						if(z == z.parent.left)	//case 2
						{
							z = z.parent;
							rightRotate(this._root,z);	//case 2转化为case 3
						}
						z.parent.color = AppConfig.BLACK;	//case 3
						z.parent.parent.color = AppConfig.RED;
						leftRotate(this._root,z.parent.parent);
					}
					
				}
			}
			this._root.color = AppConfig.BLACK;
		}
		
		
		/**
		 * 中序遍历输出 
		 * @return 
		 * 
		 */						
		public function inorderTraversal():void
		{
			inorder(this._root);
		}
		
		private function inorder(root:RBTreeNode):void
		{
			if(root == NIL) 
				return;
			inorder(root.left);
			trace(root.key + ":" + root.color + ":" + root.parent.key + ";distance is：" + root.distance + ";offsetX is:" + root.OffsetX);
			inorder(root.right);
		}
		
		/**
		 * 前序遍历输出 
		 * 
		 */		
		public function preorderTraversal():void
		{
			preorder(this._root);
		}
		
		private function preorder(root:RBTreeNode):void
		{
			if(root == null) 
				return;
			trace(root.key + ":" + root.color);
			preorder(root.left);
			preorder(root.right);
		}
		
		/**
		 * 查询 节点 
		 * @param value 查询值
		 * @return 
		 * 
		 */		
		public function search(key:int):RBTreeNode
		{
			return _search(key,this._root);
		}
		
		
		private function _search(key:int,root:RBTreeNode):RBTreeNode
		{
			if(root == NIL || root.key == key)
			{
				return root;
			}
			
			if(root.key > key)
			{
				return _search(key,root.left);
			}
			else
			{
				return _search(key,root.right);
			}
			
		}
		
		
		/**
		 * 返回最大值节点 
		 * @return 
		 * 
		 */		
		public function getMaxNode():RBTreeNode
		{
			return _getMaxNode(this._root);
		}
		
		private function _getMaxNode(root:RBTreeNode):RBTreeNode
		{
			while(root.right != NIL)
			{
				root = root.right;
			}
			return root;
		}
		
		
		/**
		 * 返回最小值节点 
		 * @return 
		 * 
		 */		
		public function getMinNode():RBTreeNode
		{
			return _getMinNode(this._root);
		}
		
		private function _getMinNode(root:RBTreeNode):RBTreeNode
		{
			while(root.left != NIL)
			{
				root = root.left;
			}
			return root;
		}
		
		/**
		 * 返回某节点的前趋节点
		 * @param node
		 * @return RBTreeNode
		 * 
		 */		
		public function predecessor(node:RBTreeNode):RBTreeNode
		{
			if(node.left != NIL)
			{
				return _getMaxNode(node.left);
			}
			var parent:RBTreeNode = node.parent;
			while(parent != NIL && node == parent.left)
			{
				node = parent;
				parent = parent.parent;
			}
			return parent;
		}
		
		
		/**
		 * 返回某节点的后继节点  
		 * @param node
		 * @return RBTreeNode
		 * 
		 */				
		public function successor(node:RBTreeNode):RBTreeNode
		{
			if(node.right != NIL)
			{
				return _getMinNode(node.right);
			}
			var parent:RBTreeNode = node.parent;
			while(parent != NIL && node == parent.right)
			{
				node = parent;
				parent = parent.parent;
			}
			return parent;
		}
		
		
		/**
		 * 删除操作 
		 * @param value
		 * @return 
		 * 
		 */		
		public function RBTreeDelete(key:int):RBTreeNode
		{
			var targetNode:RBTreeNode = search(key);	//根据k找到需要删除的目标节点
			if(targetNode.key == -1)
			{
				return null;
			}
			var tempNode:RBTreeNode,childNode:RBTreeNode;
			if(targetNode.left == NIL || targetNode.right == NIL)
			{
				tempNode = targetNode;	//直接返回目标节点
			}
			else
			{
				tempNode = successor(targetNode);	//返回目标节点的后继节点
			}
			
			if(tempNode.left != NIL)
			{
				childNode = tempNode.left;
			}
			else
			{
				childNode = tempNode.right;	//右节点为空时，childNode即null
			}
			
			
			childNode.parent = tempNode.parent;
			
			
			if(tempNode.parent == NIL)
			{
				this._root = childNode;
			}
			else if(tempNode == tempNode.parent.left)
			{
				tempNode.parent.left = childNode;
			}
			else
			{
				tempNode.parent.right = childNode;
			}
			
			if(tempNode != targetNode)
			{
				targetNode.key = tempNode.key;
			}
			
			if(tempNode.color == AppConfig.BLACK)
			{
				RBTreeDeleteFixUp(this._root,childNode);
			}
			
			return tempNode;
				
			
		}
		
		/**
		 * 删除节点操作的修复程序 
		 * 当删除的节点为黑色节点时，可能会遇到下面的情况：
		 * 1) 如果要删除的是根结点,  且根结点的一个红色孩子结点将成为新的根
		 * 2) 如果删除某个结点后, 在其原来父结点上出现连续的红结点
		 * 3) 删除某个结点后, 导致先前包含该结点的路径上黑结点数少1
		 * 
		 * 当被删除节点的子节点x是黑色的时候，需要处理四种情况：（对称，另外四种）
		 * case 1:x的兄弟w是红色的
		 * case 2:x的兄弟w是黑色的，而且w的两个孩子都是黑色的
		 * case 3:x的兄弟w是黑色的，而且w的左孩子是红色，w的右孩子是黑色的
		 * case 4:x的兄弟w是黑色的，且w的右孩子是红色的
		 * 
		 * @param root	红黑树
		 * @param x	被删除节点的子节点
		 * 
		 */		
		private function RBTreeDeleteFixUp(root:RBTreeNode,x:RBTreeNode):void
		{
			while(x != root && x.color == AppConfig.BLACK)
			{
				if(x == x.parent.left)
				{
					var w:RBTreeNode = x.parent.right;
					if(w.color == AppConfig.RED)	//case 1
					{
						w.color = AppConfig.BLACK;
						x.parent.color = AppConfig.RED;
						leftRotate(root,x.parent);
						w = x.parent.right;
					}
					//~~~~~~~~~case 2~~~~~~~~~~
					if(w.left.color == AppConfig.BLACK && w.right.color == AppConfig.BLACK)
					{
						w.color = AppConfig.RED;
						x = x.parent;
					}
					else if(w.right.color == AppConfig.BLACK)	//case 3
					{
						w.color = AppConfig.RED;
						w.left.color == AppConfig.BLACK;
						rightRotate(root,w);
						w = x.parent.right;
					}
					else	//case 4
					{
						w.color = x.parent.color;
						x.parent.color = AppConfig.BLACK;
						w.right.color = AppConfig.BLACK;
						leftRotate(root,x.parent);
						x = root;
					}
				}
					else
					{
						var w1:RBTreeNode = x.parent.left;
						if(w1.color == AppConfig.RED)
						{
							w1.color = AppConfig.BLACK;
							x.parent.color = AppConfig.RED;
							rightRotate(root,x.parent);
							w1 = x.parent.left;
						}
						
						if(w1.left.color == AppConfig.BLACK && w1.right.color == AppConfig.BLACK)
						{
							w1.color = AppConfig.RED;
							x = x.parent;
						}
						else if(w1.left.color == AppConfig.BLACK)
						{
							w1.left.color = AppConfig.BLACK;
							w1.color = AppConfig.RED;
							leftRotate(root,w1);
							w1 = x.parent.left;
						}
						else
						{
							w1.color = x.parent.color;
							x.parent.color = AppConfig.BLACK;
							rightRotate(root,x.parent);
							x = root;
						}
					}
				}
				x.color == AppConfig.BLACK;
			}
		
		/**
		 * 返回节点和根节点的距离
		 * @param node
		 * @return 
		 * 
		 */		
		public function getNodeDistance(node:RBTreeNode):int
		{
			var distance:int = 0;
			var x:RBTreeNode = this._root;
			var y:RBTreeNode = NIL;
			while(x != node && x != NIL)
			{
				if(x.key > node.key)
				{
					x = x.left;
				}
				else
				{
					x = x.right;
				}
				++ distance;
			}
			
			if(x == NIL)
			{
				distance = 0
			}
			
			return distance;
		}
		
		/**
		 * 设置所有节点的距离根节点的距离
		 * @param root
		 * 
		 */		
		public function setAllNodesDistance(root:RBTreeNode):void
		{
			if(root == NIL) 
				return;
			
			root.distance = getNodeDistance(root);
			if(root == this._root)
			{
				root.OffsetX = 0;
			}
			else
			{
				if(root == root.parent.left)
				{
					root.OffsetX = root.parent.OffsetX - 100/root.distance;
				}
				else
				{
					root.OffsetX = root.parent.OffsetX + 100/root.distance;
				}
				
			}
			setAllNodesDistance(root.left);
			setAllNodesDistance(root.right);
		}
	
		
		
		
		
		
		
		
		
		
		}
}